/**
 * 作用：利用深度优先搜索算法+栈的数据结构，解决迷宫问题。
 * 
 * 日期：2019-10-29
 * 
 * 参考：http://akaedu.github.io/book/ch12s03.html
 */
#include <stdio.h>
#include <stdlib.h>

struct point
{
    int row;
    int col
};

struct point stack[512];

int rowmax = 5, colmax = 5;

int maze[5][5] = {
    {0, 1, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0},
};

struct point pre[5][5] = {
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}},
    {{-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1},
     {-1, -1}}

};

int top = 0;

/* 压入 */
void push(struct point p)
{
    stack[top++] = p;
    return;
}

/* 弹出 */
struct point pop()
{
    return stack[--top];
}

/* 判断是否为空 */
int is_empty()
{
    return top == 0;
}

/* 函数：打印当前迷宫状态 */
void print_mem()
{
    int i = 0, j = 0;
    static int count_num = 0;

    count_num++;

    printf("---------- %d -----------\n", count_num);

    for (i = 0; i < rowmax; i++)
    {
        for (j = 0; j < colmax; j++)
        {
            printf("%4d", maze[i][j]);
        }
        printf("\n");
    }

    return;
}

void visit(int r, int c, struct point p, struct point pnext)
{
    maze[r][c] = 2;

    pnext.row = r;
    pnext.col = c;

    push(pnext);

    pre[r][c] = p;
}

int main()
{
    struct point p = {0, 0};
    struct point pnext;
    int r = 0, c = 0;

    int has_path = 1;

    r = p.row, c = p.col;

    /* 将当前元素设定为走过的值，并压入栈内 */
    maze[r][c] = 2;
    push(p);

    while (r < rowmax - 1 || c < colmax - 1)
    {
        /* 弹出栈顶元素 */
        p = pop();
        r = p.row;
        c = p.col;

        /* 搜索 */
        if (c + 1 < colmax && maze[r][c + 1] == 0) /* right */
            visit(r, c + 1, p, pnext);
        if (r + 1 < rowmax && maze[r + 1][c] == 0) /* down */
            visit(r + 1, c, p, pnext);
        if (c - 1 >= 0 && maze[r][c - 1] == 0) /* left */
            visit(r, c - 1, p, pnext);
        if (r - 1 >= 0 && maze[r - 1][c] == 0) /* up */
            visit(r - 1, c, p, pnext);

        /* 打印mem数组 */
        print_mem();

        /* 若栈内为空，并且还没达到终点，则判断没有路径。 */
        if (is_empty()) //函数做参数，不要忘了最后的小括号
        {
            has_path = 0;
            break;
        }
    }

    // ender.
    if (has_path)
    {
        printf("Succeed!\n");

        /* 回溯 */
        pnext.row = rowmax - 1;
        pnext.col = colmax - 1;

        r = pnext.row;
        c = pnext.col;
        printf("(%2d,%2d)\n", r, c);
        maze[r][c] = 3;

        while (r != 0 || c != 0)
        {
            pnext = pre[r][c];
            r = pnext.row;
            c = pnext.col;
            printf("(%2d,%2d)\n", r, c);
            maze[r][c] = 3;
        }

        printf("The path is (mark as 3):\n");
        print_mem();
    }
    else
    {
        printf("No path!\n");
    }

    return 0;
}